home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / impl / skiplist.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  4.9 KB  |  186 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  skiplist.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_SKIPLIST_H
  17. #define LEDA_SKIPLIST_H
  18.  
  19. #include <LEDA/basic.h>
  20.  
  21. //------------------------------------------------------------------------------
  22. // Pugh's skip lists
  23. //------------------------------------------------------------------------------
  24.  
  25. class skiplist_node
  26. { 
  27.   friend class skiplist;
  28.  
  29.   GenPtr key;
  30.   GenPtr inf;
  31.   int    level;
  32.   skiplist_node* pred;  
  33.   skiplist_node* backward;  
  34.   skiplist_node* forward[1];  // variable sized array of forward pointers 
  35.  
  36.  };
  37.  
  38. typedef skiplist_node* skiplist_item;
  39.  
  40.  
  41. class skiplist
  42. {  
  43.    int level;                  // maximum level
  44.    skiplist_node*  header;     // pointer to header
  45.    skiplist_item STOP;         // pointer to end 
  46.    int randomBits;             // random bit source
  47.    int randomsLeft;            // number of unused bit pairs in randomBits
  48.    int count;                  // number of entries
  49.  
  50.    float prob;                 
  51.  
  52.    int  randomLevel();
  53.  
  54. virtual int cmp(GenPtr x, GenPtr y) const { return compare(x,y); }
  55. virtual void copy_key(GenPtr&)  const {}
  56. virtual void copy_inf(GenPtr&)  const {}
  57. virtual void clear_key(GenPtr&) const {}
  58. virtual void clear_inf(GenPtr&) const {}
  59. virtual void print_key(GenPtr)  const {}
  60. virtual void print_inf(GenPtr)  const {}
  61.  
  62. virtual int int_type()    const { return 0; }
  63.  
  64. skiplist_item search(GenPtr,int&) const;
  65. void          remove_item(skiplist_item);
  66. void          insert_item_at_item(skiplist_item,skiplist_item);
  67.  
  68. protected:
  69.  skiplist_item item(void* p) const { return skiplist_item(p); }
  70.  
  71. public:
  72.  
  73.  skiplist(float prob = 0.25);
  74.  skiplist(const skiplist&);
  75.  skiplist& operator=(const skiplist&);
  76.  virtual ~skiplist();
  77.  
  78.  GenPtr key(skiplist_item p) const;
  79.  GenPtr inf(skiplist_item p) const;
  80.  GenPtr& info(skiplist_item p) const;
  81.  int     get_level(skiplist_item p) const;
  82.  
  83.  skiplist_item insert(GenPtr key, GenPtr inf);
  84.  skiplist_item locate(GenPtr key) const;
  85.  skiplist_item locate_succ(GenPtr key) const;
  86.  skiplist_item locate_pred(GenPtr key) const;
  87.  skiplist_item lookup(GenPtr key) const;
  88.  skiplist_item min() const;
  89.  skiplist_item max() const;
  90.  void          reverse_items(skiplist_item,skiplist_item);
  91.  void          del(GenPtr key);
  92.  void          del1(GenPtr key);
  93.  
  94.  void          conc(skiplist&);
  95.  void          split_at_item(skiplist_item,skiplist&,skiplist&);
  96.  
  97.  void          print();
  98.  
  99.  skiplist_item insert_at_item(skiplist_item p, GenPtr key, GenPtr inf);
  100.  
  101.  skiplist_item insert1(GenPtr key, GenPtr inf);
  102.  
  103.  
  104.  void          change_inf(skiplist_item p, GenPtr inf);
  105.  void          del_item(skiplist_item p);
  106.  void          clear();
  107.  int           size() const;
  108.  int           empty() const;
  109.  
  110.  skiplist_item first_item() const;
  111.  skiplist_item next_item(skiplist_item p) const;
  112.  skiplist_item succ(skiplist_item p) const;
  113.  skiplist_item pred(skiplist_item p) const;
  114.  
  115.  
  116.  // piority queue operations
  117.  
  118.  skiplist_item find_min() const;
  119.  void del_min();
  120.  void decrease_key(skiplist_item p, GenPtr k);
  121.  
  122.  
  123. };
  124.  
  125.  
  126.  
  127.  
  128. inline GenPtr  skiplist::key(skiplist_item p) const { return p->key; }
  129. inline GenPtr  skiplist::inf(skiplist_item p) const { return p->inf; }
  130. inline GenPtr& skiplist::info(skiplist_item p) const { return p->inf; }
  131.  
  132. inline int     skiplist::get_level(skiplist_item p) const { return p->level; }
  133.  
  134.  
  135. inline skiplist_item skiplist::first_item() const  
  136. { skiplist_item q = header->forward[0];
  137.   return (q==STOP) ? 0 : q;
  138.  }
  139.  
  140. inline skiplist_item skiplist::min() const  
  141. { skiplist_item q = header->forward[0];
  142.   return (q==STOP) ? 0 : q;
  143.  }
  144.  
  145. inline skiplist_item skiplist::max() const  
  146. { skiplist_item q = STOP->pred;
  147.   return (q==header) ? 0 : q;
  148.  }
  149.  
  150. inline skiplist_item skiplist::next_item(skiplist_item p) const 
  151. { skiplist_item q =  p->forward[0]; 
  152.   return (q==STOP) ? 0 : q;
  153.  }
  154.  
  155. inline skiplist_item skiplist::succ(skiplist_item p) const 
  156. { skiplist_item q =  p->forward[0]; 
  157.   return (q==STOP) ? 0 : q;
  158.  }
  159.  
  160. inline skiplist_item skiplist::pred(skiplist_item p) const 
  161. { skiplist_item q =  p->pred; 
  162.   return (q==header) ? 0 : q;
  163.  }
  164.  
  165. inline void skiplist::change_inf(skiplist_item p, GenPtr inf) { p->inf = inf; }
  166. inline int  skiplist::size() const { return count; }
  167. inline int  skiplist::empty() const { return count==0; }
  168.  
  169. //priority queue
  170. inline skiplist_item skiplist::find_min() const { return min(); }
  171.  
  172. inline void skiplist::del_min() 
  173. { skiplist_item p = min(); if (p) del_item(p); }
  174.  
  175. inline void skiplist::decrease_key(skiplist_item p, GenPtr k) 
  176. { insert(k,p->inf); del_item(p);}
  177.  
  178.  
  179. // dummy I/O and cmp functions
  180.  
  181. inline void Print(const skiplist&,ostream&) { }
  182. inline void Read(skiplist&, istream&) { }
  183. inline int  compare(const skiplist&,const skiplist&) { return 0; }
  184.  
  185. #endif
  186.